#pragma once
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int cmp(const void *p1, const void *p2)
{
    if (*((float *)p1) < *((float *)p2))
        return -1;
    if (*((float *)p1) > *((float *)p2))
        return 1;
    if (*((float *)p1) == *((float *)p2))
        return 0;
}
void test()
{
    // 计算机算法分析与设计p8 1-5
    // 最大间隙问题
    // 解法1
    float arr[] = {2.3, 3.1, 7.5, 1.5, 6.3};
    qsort(arr, sizeof(arr) / sizeof(int), sizeof(int), cmp);
    for (auto s : arr)
    {
        std::cout << s << " ";
    }
    std::cout << std::endl;
    double max = 0;
    int n = sizeof(arr) / sizeof(int);
    for (int i = 1; i < n; i++)
    {
        double tmp = fabs(arr[i] - arr[i - 1]);
        if (tmp > max)
            max = tmp;
    }
    std::cout << "最大间隙为: " << max << std::endl;
    // 解法2
    // 鸽巢原理待解
}
void dfs(vector<int> &a, vector<int> &b, vector<int> &c, int n)
{
    if (n == 1)
    {
        c.push_back(a.back());
        a.pop_back();
        return;
    }
    dfs(a, c, b, n - 1);
    c.push_back(a.back());
    a.pop_back();
    dfs(b, a, c, n - 1);
}
void hannuota(vector<int> &a, vector<int> &b, vector<int> &c)
{
    dfs(a, b, c, a.size());
}
void test1()
{
    // 汉诺塔问题
    vector<int> a{8, 7, 6, 5, 4, 3, 2, 1, 0};
    vector<int> b;
    vector<int> c;
    hannuota(a, b, c);
    for (auto c1 : c)
    {
        cout << c1 << " ";
    }
    cout << endl;
}
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;
        ListNode *newhead = new ListNode();
        ListNode *newtail = newhead;
        ListNode *l1 = list1;
        ListNode *l2 = list2;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                newtail->next = l1;
                l1 = l1->next;
            }
            else
            {
                newtail->next = l2;
                l2 = l2->next;
            }
            newtail = newtail->next;
        }
        if (l1)
        {
            newtail->next = l1;
        }
        if (l2)
        {
            newtail->next = l2;
        }
        ListNode *ret = newhead->next;
        delete newhead;
        newhead = nullptr;
        return ret;
    }
};
void test21()
{
    ListNode *list1 = new ListNode(1);
    ListNode *tail1 = list1;
    for (int i = 2; i < 11; i++)
    {
        tail1->next = new ListNode(i);
        tail1 = tail1->next;
    }
    ListNode *list2 = new ListNode(1);
    ListNode *tail2 = list2;
    for (int i = 2; i < 11; i++)
    {
        tail2->next = new ListNode(i);
        tail2 = tail2->next;
    }
    ListNode *cur1 = list1;
    for (int i = 1; i < 11; i++)
    {
        std::cout << cur1->val << " ";
        cur1 = cur1->next;
    }
    std::cout << std::endl;
    ListNode *cur2 = list2;
    for (int i = 1; i < 11; i++)
    {
        std::cout << cur2->val << " ";
        cur2 = cur2->next;
    }
    std::cout << std::endl;
    Solution sol;
    ListNode *h = sol.mergeTwoLists(list1, list2);
    while (h)
    {
        std::cout << h->val << " ";
        h = h->next;
    }
    std::cout << std::endl;
}
void test22()
{
    class Solution
    {
    public:
        ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
        {
            if (list1 == nullptr)
                return list2;
            if (list2 == nullptr)
                return list1;
            if (list1->val <= list2->val)
            {
                list1->next = mergeTwoLists(list1->next, list2);
                return list1;
            }
            else
            {
                list2->next = mergeTwoLists(list1, list2->next);
                return list2;
            }
        }
    };
}
void test2()
{
    // 合并两个有序链表
    // 解法1
    test21();
    // 解法2
    // 递归
    // 重复子问题:合并两个有序链表
    test22();
}